//
// Description: 5841. 找出到每个位置为止最长的有效障碍赛跑路线
// Created by Loading on 2021/8/8.
//

#include <bits/stdc++.h>

using namespace std;

vector<int> longestObstacleCourseAtEachPosition(vector<int> &obstacles) {
    /* 题目理解为求到每个位置为止，必须包含当前位置障碍的最长不递减子序列 */
    vector<int> res, maxLen_increase;

    for (auto &x : obstacles) {
        // 最长不递减子序列为空 或 当前障碍高度大于等于子序列的最后一个，直接追加
        if (maxLen_increase.empty() || x >= maxLen_increase.back()) {
            maxLen_increase.emplace_back(x);
            res.emplace_back(maxLen_increase.size());
            continue;
        }

        // 二分查找第一个大于等于当前障碍高度的位置
        auto it = upper_bound(maxLen_increase.begin(), maxLen_increase.end(), x);
        // 插入长度
        res.emplace_back(it - maxLen_increase.begin() + 1);
        // 此位置更新为此障碍高度的值，保证当前值较小，后续子序列更长
        *it = x;
    }

    return res;
}

int main() {
    vector<int> obstacles = {1, 2, 3, 2};
    vector<int> res = longestObstacleCourseAtEachPosition(obstacles);
    for (auto &x : res) {
        cout << x << " ";
    }
    cout << endl;
}